#include <iostream>
#include <vector>
#include "lib/binary_tree.h"
using namespace std;

void findPathCore(BinaryTreeNode* root,
                  const int &sum,
                  int &cur_sum,
                  vector<vector<int>> &rets,
                  vector<int> &ret) {
  if (!root)
    return;
  
  cur_sum += root->value;
  ret.push_back(root->value);
  bool isLeft = !root->left && !root->right;
  if (isLeft && cur_sum == sum) {
    rets.push_back(ret);
  }

  findPathCore(root->left, sum, cur_sum, rets, ret);
  findPathCore(root->right, sum, cur_sum, rets, ret);
  cur_sum -= root->value;
  ret.pop_back();
}

vector<vector<int>> findPath(BinaryTreeNode* root, const int &sums) {
  vector<vector<int>> rets;
  vector<int> ret;
  int sum = 0;
  findPathCore(root, sums, sum, rets, ret);
  return rets;
}

int main() {
  vector<int> vec = {10, 5, 12, 4, 7};
  BinaryTreeNode* root = CreateBinaryTree(vec);

  vector<vector<int>> rets = findPath(root, 22);
  for (size_t i = 0; i < rets.size(); ++i) {
    for (size_t j = 0; j < rets[i].size(); ++j) {
      cout << rets[i][j] << " ";
    }
    cout << endl;
  }

  DeleteBinaryTree(root);

  return 0;
}
